# -*- coding: utf-8 -*-
'''
@author: Luís Shou nº 5601
@date: Maio de 2013
'''

import sys

class MergeSort:
    '''
    Classe do algoritmo MergeSort
    '''
    def __init__(self, A, p, r):
        '''
        Construtor da classe.

        Parametros de entrada:
                    A - Lista com elementos a ordenar
                    p - Posição inicial da tabela[0]
                    r - Posição final da tabela
        '''
        self.A = A
        self.p = p
        self.r = r
        self.merge_sort(self.p, self.r)
        pass
   
    def merge(self, p, q, r):
        '''
        Método para ordenar as tabelas 
        que foram criadas pelo método merge_sort

        Método merge
        Aqui serão feitas duas sub-tabelas da tabela A
       
        Parametros: 'p' - Indice da tabela A
                    'q' - Indice da tabela A
                    'r' - Indice da tabela A
        '''
        n1 = q - p + 1
        n2 = r - q

        L = [0 for i in range(n1+1)]
        R = [0 for j in range(n2+1)]

        for i in range(0, n1):
            L[i] = self.A[p + i]
            pass

        for j in range(0, n2):
            R[j] = self.A[q + j + 1]
            pass

        L[n1] = sys.maxint
        R[n2] = sys.maxint

        i = 0
        j = 0
        for k in range(p, r + 1):
            if L[i] <= R[j]:
                self.A[k] = L[i]
                i += 1
            else:
                self.A[k] = R[j]
                j += 1

    def merge_sort(self, p, r):
        '''
        Método que divide a lista em duas tabelas
        para depois ordena-las.
       
        Parametros: 'p' - Indice da tabela A
                    'r' - Indice da tabela A
        '''
        if p < r:
            q = (p + r) / 2
            self.merge_sort(p, q)
            self.merge_sort(q + 1, r)
            self.merge(p, q, r)
